//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 105] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 栈 递归 链表 双指针 
// 👍 1163 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Stack;

public class PalindromeLinkedList {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(1);
        ListNode node4 = new ListNode(2,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(3,node3);
        ListNode node1 = new ListNode(2,node2);
        ListNode head = new ListNode(1,node1);
        boolean flag = new PalindromeLinkedList().new Solution().isPalindrome(head);
    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        /*//我自己写的，使用的栈，时间复杂度我不知道为什么还那么高，空间复杂度确实高
        if (head == null || head.next == null) return true;
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while (p!=null){
            stack.push(p);
            p = p.next;
        }
        p = head;
        int i = stack.size()/2;//小优化，时间少点
        while (p!=null && i!= 0){
            if (p.val != stack.pop().val) return false;
            p = p.next;
            i--;
        }
        return true;*/
        if(head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;//快指针用于遍历原始链表，每次向前移动两个节点
        ListNode slow = head;//慢指针用于存储链表后半部分的元素
        ListNode pre = null;//pre用于逆序存储链表的前半部分节点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode temp = slow.next;//这里用temp来存放slow之后的所有顺序节点
            slow.next = pre;//用于拼接逆序链表
            pre = slow;//将pre指向逆序链表
            slow = temp;//slow指向剩下的原始链表
        }
        if(fast != null) {//这里说明原始链表元素有奇数个，需要将slow再前进一位，跳过中间节点
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}